package com.demo.study.algorithm.search;

/**
 * 插值查找
 *
 * @author Baymax
 * @since 2024-08-13
 */
public class A03_InsertSearch {
    public static void main(String[] args) {
        int[] array = new int[]{2, 6, 6, 6, 6, 10, 14, 15, 24, 24, 30};
        System.out.println(insertSearchBase(array, 0, array.length - 1, 20));
    }

    /**
     * 插值查找：在二分查找的基础上，修改中间索引计算方式，修改为自适应取值
     */
    public static int insertSearchBase(int[] array, int leftIndex, int rightIndex, int target) {
        // 最大值&最小值保护校验，否则会报错
        if (array[0] > target || array[array.length - 1] < target) {
            return -1;
        }
        if (leftIndex >= rightIndex) {
            return -1;
        }
        // 自适应查找顺序
        int m = leftIndex + (rightIndex - leftIndex) * (target - array[leftIndex]) / (array[rightIndex] - array[leftIndex]);
        int mValue = array[m];
        if (target < mValue) {
            return insertSearchBase(array, leftIndex, m - 1, target);
        } else if (mValue < target) {
            return insertSearchBase(array, m + 1, rightIndex, target);
        } else {
            return m;
        }
    }
}
